public class U_5_3 {
    static int n = 16;
    //在此初始化有向图
    static int[][] arr = {};

    public static void shortPath(int arr[][]) {
        int i = 1;
        int sum = 0;
        int temp = 0;
        int[] p = new int[n];
        int[] len = new int[n];
        while (i < n) {
            int total = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++)
                if (arr[j][i] != 0) {
                    if (total > (arr[j][i] + len[j])) {
                        total = arr[j][i] + len[j];
                        temp = j;
                    }
                    len[i] = total;
                    sum = total;
                    p[i] = temp;
                }
            i++;
        }
        int[] path = new int[7];
        path[0] = 0;
        path[6] = 15;
        for (int k = 5; k >= 1; k--)
            path[k] = p[path[k + 1]];
        System.out.println("最短路径为：");
        for (int m = 0; m < 6; m++)
            System.out.print(path[m] + "->");
        System.out.println(path[6]);
        System.out.println("最小代价为：" + sum);
    }
}





